
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/43.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">省选の反思</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <p>
<script type="math/tex; mode=display">\color{orange}\Huge\text{『技不如人，甘拜下风!!!』}</script>
<del>这个屑因为太屑以至于被 <script type="math/tex">\rm unrated</script> ！！！</del></p>
<p>
<script type="math/tex">\rm u1s1</script>,<script type="math/tex">\rm ccf</script> 造数据水平天下第一！！！</p>
<h2 id="colorgreentextp7514-2021-ab"><a href="https://www.luogu.com.cn/problem/P7514"><script type="math/tex">\color{green}\text{P7514 [省选联考 2021 A/B 卷] 卡牌游戏}</script></a></h2>
<p><del>考场上只想到阴间二分，不知道对不对就不管了。</del></p>
<p>多打两个等号 <script type="math/tex">\rm 100pts\to 0pts</script>
</p>
<p>好像有一点小问题在 <script type="math/tex">\rm UOJ</script> 上被 <script type="math/tex">\rm\color{red}Extra\ Test</script> 叉掉了，以后再补。。。</p>
<h2 id="colorgreentextp7515-2021-a"><a href="https://www.luogu.com.cn/problem/P7515"><script type="math/tex">\color{green}\text{P7515 [省选联考 2021 A 卷] 矩阵游戏}</script></a></h2>
<p>
<script type="math/tex; mode=display">\color{red}\text{被一个差分约束打爆了}</script>
考场上想到差分约束，但因为不知道怎么处理 <script type="math/tex">(n,m)</script> 没敢写。</p>
<p>大概就是先令最后一行最后一列为 <script type="math/tex">0</script>,构造出 <script type="math/tex">a_0</script>，然后此时的 <script type="math/tex">a_0</script> 会有一些不符合条件的，需要调整来复合条件。</p>
<p>发现给一行或一列 <script type="math/tex">+1,-1,+1,-1,\ldots</script>，不影响得到的 <script type="math/tex">b</script> 的值。假设给第 <script type="math/tex">i</script> 行第一个更改 <script type="math/tex">x_i</script>，给第 <script type="math/tex">i</script> 列第一个更改 <script type="math/tex">y_i</script>，得到新的 <script type="math/tex">a^\prime</script>:
<script type="math/tex; mode=display">
a_0+\begin{pmatrix}
x_1+y_1&-x1+y_2&x_1+y_3&-x_1+y_4&\dots\\
x_2-y_1&-x_2-y_2&x_2-y_3&-x_2-y_4&\dots\\
x_3+y_1&-x_3+y_2&x_3+y_3&-x_3+y_4&\dots\\
x_4-y_1&-x_4-y_2&x_4-y_3&-x_4-y_4&\dots\\
\vdots&\vdots&\vdots&\vdots&\ddots
\end{pmatrix}
</script>
当时拼命在想调整最后一行和一列就没做出来，因为这样每个位置会涉及到 <script type="math/tex">3</script> 个变量无法使用差分约束。</p>
<p>虽然现在还是不行，因为有和式。我们可以把奇数行的 <script type="math/tex">x</script> 取相反数，偶数列的 <script type="math/tex">y</script> 取相反数，就是：
<script type="math/tex; mode=display">
a_0+\begin{pmatrix}
-x_1+y_1&x1-y_2&-x_1+y_3&x_1-y_4&\dots\\
x_2-y_1&-x_2+y_2&x_2-y_3&-x_2+y_4&\dots\\
-x_3+y_1&x_3-y_2&-x_3+y_3&x_3-y_4&\dots\\
x_4-y_1&-x_4+y_2&x_4-y_3&-x_4+y_4&\dots\\
\vdots&\vdots&\vdots&\vdots&\ddots
\end{pmatrix}
</script>
差分约束随便跑啊啊啊啊啊</p>
<h2 id="colorgreentextp7516-2021-ab"><a href="https://www.luogu.com.cn/problem/P7516"><script type="math/tex">\color{green}\text{P7516 [省选联考 2021 A/B 卷] 图函数}</script></a></h2>
<p>
<script type="math/tex; mode=display">\color{red}\text{被一个最短路打爆了}</script>
</p>
<p>
<script type="math/tex">H(G)</script> 好像意思是说，有多少 <script type="math/tex">(u,v)</script> 使得 <script type="math/tex">u,v</script> 双向可达且经过点的编号大于等于 <script type="math/tex">v</script>
<script type="math/tex">(u\ge v)</script>。</p>
<p>这个转化看上去就非常牛逼，但是为什么是对的呢？</p>
<p>不难发现 <script type="math/tex">(u,1)</script> 是成立的。那么 <script type="math/tex">(u,2)</script> 不能经过 <script type="math/tex">1</script>。如果 <script type="math/tex">u\to2\to u</script> 经过 <script type="math/tex">1</script>，那么就可以形成环 <script type="math/tex">u\to1\to u</script>。同理 <script type="math/tex">(u,3)</script> 不能经过 <script type="math/tex">1,2</script>， <script type="math/tex">(u,v)</script> 不能经过 <script type="math/tex">[1,v)</script>
</p>
<p>现在的复杂度应该是 <script type="math/tex">O(mn^3)</script> 的，可能甚至和暴力同分。考虑把删边改成加边，一个 <script type="math/tex">(u,v)</script> 什么时候 <strong>开始</strong> 有贡献？感性理解为 <script type="math/tex">(u,v)</script> 可以通过编号大于等于 <script type="math/tex">v</script> 的点到达的最早时间。而经过的点编号大于等于 <script type="math/tex">v</script> 可以简单地用 <script type="math/tex">\rm Floyd</script> 约束。</p>
<p>裸的 <script type="math/tex">\rm Floyd</script> 在 <script type="math/tex">\rm LOJ</script> 上是可以过的，但在洛谷上被卡常了。</p>
<h2 id="colorgreentextp7518-2021-ab"><a href="https://www.luogu.com.cn/problem/P7518"><script type="math/tex">\color{green}\text{P7518 [省选联考 2021 A/B 卷] 宝石}</script></a></h2>
<p>不仅套路而且**</p>
<p>倍增即可。</p>
<h2 id="colorgreentextp7519-2021-ab"><a href="https://www.luogu.com.cn/problem/P7519"><script type="math/tex">\color{green}\text{P7519 [省选联考 2021 A/B 卷] 滚榜}</script></a></h2>
<p>这道只有 <script type="math/tex">35</script> 行的丝啵题竟然没做出来，果然是退役了。</p>
<p>还是先转化，首先每一个 <script type="math/tex">b</script> 肯定是越小越好，剩下的加到最后一个即可。</p>
<p>然后假如上一个位置是 <script type="math/tex">j</script> 加了 <script type="math/tex">b</script>，现在到 <script type="math/tex">k</script>，那么这一次就要加 <script type="math/tex">\max(b,b+[j<k]+a[j]-a[k])</script>。</p>
<p>感觉像差分的形式，<script type="math/tex">b^\prime=b+\max(0,[j<k]+a[j]-a[k])</script>。假设还剩 <script type="math/tex">a</script> 个，那么 <script type="math/tex">\max(0,[j<k]+a[j]-a[k])</script> 就会算 <script type="math/tex">a</script> 遍。</p>
<p>然后就可以 <script type="math/tex">\rm dp</script> 了。</p>
<h2 id="colorgreentextp7520-2021-a"><a href="https://www.luogu.com.cn/problem/P7520"><script type="math/tex">\color{green}\text{P7520 [省选联考 2021 A 卷] 支配}</script></a></h2>
<p>先建立支配树，支配树上一个点的支配集变化整棵子树变化。</p>
<p>考虑一个点不再受父亲支配，则有一条 <script type="math/tex">1\to s,t\to x</script> 且不经过 <script type="math/tex">fa_x</script> 的路线，预处理一下。</p>
<p>然后计算一下贡献就做完了。
<script type="math/tex; mode=display">\Huge\color{orange}\text{『}\mathbb{AFO}\text{』}</script>
</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P2767.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\P7468.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">省选の反思</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-04-16 12:31:19</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
